// Package _0__I__斐波那契数列 main
// @Title _0__I__斐波那契数列
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-01-12 10:48
// @Create  2022-01-12 10:48
package main

import "fmt"

func fib(n int) int {
	const mod int = 1e9 + 7
	if n < 2 {
		return n
	}
	p, q, r := 0, 0, 1
	for i := 2; i <= n; i++ {
		p = q
		q = r
		r = (p + q) % mod
	}
	return r
}

func oldFib(n int) int {
	if n < 2 {
		return n
	}
	return oldFib(n-1) + oldFib(n-2)

}

func main() {
	//for i := 0; i < 10; i++ {
	//	fmt.Println(i," = ",fib(i))
	//}
	fmt.Println(fib(45))
	//fmt.Println(oldFib(45))

}
